In a multiprocessor system, the functional characteristics of the interprocessor interconnection medium are a significant constraint on system performance. Characteristics sought in the medium include fast access arbitration, fair arbitration (i.e., no unit is starved for access), independence of connections (i.e., a connection between some units does not constrain connections between other units), deadlock prevention, equal opportunity for a processor to send and to receive, and modular growth capability.
It is preferable to use a non-blocking medium--one that allows any interconnection that the processors are capable of handling to be made at any time. Such a medium is most versatile and efficient, in that it does not limit the type and number of interconnections between processors that may be made. It therefore delays the establishment of inter-processor connections the least of any interconnection arrangement. Also, because it allows a plurality of independent connections to exist at a time, such a medium achieves higher communication bandwidth than other media (e.g., a bus). Furthermore, non-blocking media (such as a crossbar switch, for example) permit direct connection between a source and destination, and therefore do not suffer from the latency of message or packet-passing arrangements wherein establishment of connections depends on self-routing information that must be picked off, decoded, and acted upon to effect proper routing.
Because a non-blocking interconnection medium such as a crossbar switch theoretically allows any desired connection between any processors to be made at any time, arbitration of access to the medium itself is not necessary. This situation is unlike typical bus arbitration. In single bus arbitration, the bus is the resource in demand and the destination unit, e.g., processor, is assumed by the arbiter to be available. Conversely, in the situation of a non-blocking interconnection medium, the medium is assumed to be available and the destination unit, or the link(s) connecting the destination unit to the medium, is the resource in demand.
Contention for the destination units, e.g., processors, or their links to the medium, occurs because the units or links themselves may not be capable of handling simultaneous connections from a plurality of units wishing to connect thereto. For example, a processor is typically capable of being communicatively connected to only one other processor at any one time. Hence, there remains the need to arbitrate conflicting multiple requests for access to a unit or link.
Many different arbitration arrangements are known in the art. For example, centralized arbitration in a central control unit has been practiced in conjunction with crossbar switches in computer and telephone systems. Although centralized controller arbitration arrangements operate suitably to perform their intended function, they are not always desirable, because of the inherent system complexity resulting from the many interconnections required between the controller, the interconnection medium, and the interconnected units. Also, the centralized arrangements tend to be slower and more complex than other arrangements, and they typically do not allow for modular growth of the system. Furthermore, a reliability problem exists with such arrangements, since a malfunction of the controller may remove the whole system from operation. While it is true that this fault intolerance may be overcome by means of replicating the central control unit, it is an expensive and complex proposition.
It is known to use distributed arbitration arrangements, in which a central controller is not used to determine access and instead the interaction of the requesting units determines access in the event of simultaneous requests. Such distributed arrangements are often preferable, since the expense, complexity, and slowness of, and the reliability problems associated with, the centralized controller arrangements are avoided while modular growth of the system is facilitated. But an efficient arrangement of this nature that could be applied to a nonblocking medium such as a crossbar switch and provide fair arbitration, i.e., arbitration which does not favor certain processors in their access requests while "starving out" other processors from requested access, and one which eases bottlenecks and also eliminates the possibility of deadlock between processors, has not been available.